package main.Q1401_1500;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Q1401_1410 {
    public static void main(String[] args) {
        System.out.println("Question1401：");
        System.out.println("Question1402：做菜顺序");
        System.out.println("Question1403：");
        System.out.println("Question1404：");
        System.out.println("Question1405：最长快乐字符串");
        System.out.println("Question1406：");
        System.out.println("Question1407：");
        System.out.println("Question1408：");
        System.out.println("Question1409：查询带键的排列");
        System.out.println("Question1410：");
    }
}

class Question1402 {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int[][] dp = new int[satisfaction.length][satisfaction.length];
        int max = 0;
        for (int i = 0; i < satisfaction.length; i++) {
            int index = 1, total = 0;
            for (int j = i; j < satisfaction.length; j++) {
                if (i == j) {
                    dp[i][j] = index * satisfaction[j];
                } else {
                    dp[i][j] = dp[i][j - 1] + satisfaction[j] * index;
                }
                index++;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}

class Question1405 {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> q = new PriorityQueue<>((x, y)->y[1]-x[1]);
        if (a > 0) q.add(new int[]{0, a});
        if (b > 0) q.add(new int[]{1, b});
        if (c > 0) q.add(new int[]{2, c});
        StringBuilder result = new StringBuilder();
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int n = result.length();
            if (n >= 2 && result.charAt(n - 1) - 'a' == cur[0] && result.charAt(n - 2) - 'a' == cur[0]) {
                if (q.isEmpty()) break;
                int[] next = q.poll();
                result.append((char)(next[0] + 'a'));
                if (--next[1] != 0) q.add(next);
                q.add(cur);
            } else {
                result.append((char)(cur[0] + 'a'));
                if (--cur[1] != 0) q.add(cur);
            }
        }
        return result.toString();
    }
}

class Question1409 {
    public int[] processQueries(int[] queries, int m) {
        int len = queries.length;
        int[] result = new int[len];
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= m; i++) list.add(i);//初始化P数组
        for (int i = 0; i < len; i++) {//遍历queries数组
            Integer num = queries[i];
            int index = list.indexOf(num);//获取该数下标
            list.remove(index);//删除该数
            list.add(0, num);//头部添加该数
            result[i] = index;
        }
        return result;
    }
}